package com.example.demo.suanfa_sort;

import org.junit.Test;

/**
 * @program: java_base
 * @description: 小和问题
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/11 15:39
 */
public class SmallSumDemo {

    /**
     * 题目释义：
     * 数组 每个元素 左边比他小的累加和  的 和
     * 最小和？
     *
     * ////
     * 每个数右边有多少个数，比本身大(对照逆序对ReversePairDemo)
     */
    @Test
    public void smallSum() {
//        int[] arr = {1,1,3,2,1,1,1,1,1,1,2,1};
        int[] arr = {2,2,3,2,2,2,2,2,1,1,2,1};
        int process = process(arr, 0, arr.length-1);
        System.out.println(process);
    }

    public int process(int[] arr,int l,int r){
        if (l == r){
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid)
                + process(arr, mid + 1, r)
                + merge_first_try(arr, l, mid, r);
    }

    /**
     * small sum
     * 利用归并排序；排序好的位置不必在动
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     * @return
     */
    public int merge_first_try(int[] arr, int l, int mid, int r) {
        // 排序过程中， 正在比较时，左侧小数，右侧有几个比此小数大，小数*右侧大（次数） = smallSum
        int sumSmall = 0;

        int[] retArr = new int[arr.length];
        int i = 0;
        int s0 = l;
        int s1 = mid + 1;
        while (s0 <= mid && s1 <= r) {
            // 比较奇怪，为什么下两行有同样的结果，理应到  arr[s0] *= (r - s1 + 1) 错   ？
//            sumSmall += arr[s0] < arr[s1] ? arr[s0] *= (r - s1 + 1) : 0;
            sumSmall += arr[s0] < arr[s1] ? arr[s0] * (r - s1 + 1) : 0;
            retArr[i++] = arr[s0] < arr[s1] ? arr[s0++] : arr[s1++];
        }

        while (s0 <= mid) {
            retArr[i++] = arr[s0++];
        }
        while (s1 <= r) {
            retArr[i++] = arr[s1++];
        }

        // i为下一个索引位置 顾  i = index + 1 ，需要刨除==0位置
        i -= 1;
        while (i >= 0) {
            arr[r--] = retArr[i--];
        }
        return sumSmall;
    }


}
